package com.zjsru.leetcode75.level1;

/**
 * @Author: cookLee
 * @Date: 2023-10-02
 * 字符串的最大公因子
 */
public class GcdOfStrings {
    /**
     * 主
     * 输入：str1 = "ABCABC", str2 = "ABC"
     * 输出："ABC"
     * \
     * 输入：str1 = "ABABAB", str2 = "ABAB"
     * 输出："AB"
     * \
     * 输入：str1 = "LEET", str2 = "CODE"
     * 输出：""
     * @param args args
     */
    public static void main(String[] args) {
        GcdOfStrings gcdOfStrings = new GcdOfStrings();
        String str1 = "ABCABC";
        String str2= "ABC";
        System.out.println(gcdOfStrings.gcdOfStrings(str1, str2));

    }

    public String gcdOfStrings(String str1, String str2) {
        int len1 = str1.length(), len2 = str2.length();
        for (int i = Math.min(len1, len2); i >= 1; i--) {
            //两个字符串长度的约数才能满足条件
            if (len1 % i == 0 && len2 % i == 0) {
                String ans = str1.substring(0, i);
                if (this.helper(ans, str1) && this.helper(ans, str2)) {
                    return ans;
                }
            }
        }
        return "";
    }

    private boolean helper(String ans, String str) {
        int len = str.length() / ans.length();
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= len; i++) {
            sb.append(ans);
        }
        return sb.toString().equals(str);
    }

}
